3D Face Modeling, Analysis and Recognition by Daoudi Mohamed Srivastava Anuj Veltkamp Remco & Anuj Srivastava & Remco Veltkamp

Author:Daoudi, Mohamed, Srivastava, Anuj, Veltkamp, Remco & Anuj Srivastava & Remco Veltkamp [Daoudi, Mohamed, Srivastava, Anuj, Veltkamp, Remco & Srivastava, Anuj & Veltkamp, Remco]
Language: eng
Format: epub
ISBN: 9781118592632
Publisher: Wiley
Published: 2013-05-23T14:00:00+00:00

Stability of facial fiducial points and measurements under changes following facial expressions is a fundamental issue for recognition. It has been demonstrated that geodesic distances are almost preserved under many expressions (Bronstein et al., 2005). Experimental evidence of this fact has been reported in Mpiperis et al. (2006), where the maximum change of 5% is measured for the geodesic distances computed between the nose and the cheek of the same subject under different expressions. Similar results are reported in Bronstein et al. (2007), where the average standard deviation of the absolute distance error due to facial expressions was measured in 5.89 mm and 12.03 mm, respectively, for the geodesic and Euclidean distance. Moreover, the pronasale (i.e., the nose tip) and the left and right endocanthion (i.e., the points at the inner commissure of the left and right eye fissure) have been verified to be stable with respect to face variations (Bronstein et al., 2005; Chang et al., 2005).

3.9.1 Extraction of Facial Stripes

In the proposed approach, computation of the geodesic distance on the piecewise planar mesh is accomplished through the Dijkstra’s algorithm (Cormen et al., 2001), and approximates the actual geodesic distance between two surface points with the length of the shortest piecewise linear path on mesh edges. In particular, considering a mesh as a graph G=(V, E) with the edge weights w(e), w(e)>0, for each edge , the Dijkstra’s algorithm solves the problem to find the shortest path from a source vertex to a target vertex . In our specific case, the weight w(eij) of an edge eij=(vi, vj) connecting vertices vi and vj, is given by the linear length of the edge itself, that is, w(eij)=|vi−vj|. It is worth noting that the computation of geodesic distances on the mesh can be affected by the regularity of the mesh. In fact, since the Djikstra’s algorithm approximates the actual geodesic distances through edge lengths, a nontriangular mesh (i.e., a mesh composed of general polygons) or a nonregular mesh (i.e., a mesh composed of triangles of different sizes) makes the estimate less accurate. So, a mesh should be preprocessed to triangularize and regularize its polygons, thus making sufficiently accurate the computation of the geodesic distance using the Dijkstra’s approximation (Antini et al., 2005).

Computer Implementation

A pseudo-code description of the Dijkstra’s algorithm is reported in Figure 3.28. In this simple implementation, vertices of the set v are stored in an ordinary linked list (or array), and extract minimum from v is simply a linear search through all vertices in v. In this case, it can be easily shown that if |V| and |E| are the number of vertices and edges in v and E, respectively, the algorithm runs with a worst case time complexity of O(|V|2+|E|)=O(|V2|). For sparse graphs, that is, graphs with far fewer than O(|V|2) edges, Dijkstra’s algorithm can be implemented more efficiently by storing the graph in the form of adjacency lists and using a binary heap as a priority queue to implement extracting minimum efficiently. With a binary heap, the